/*
 * @lc app=leetcode.cn id=363 lang=golang
 *
 * [363] 矩形区域不超过 K 的最大数值和
 */

// 2. error 15/36
// @lc code=start
func maxSumSubmatrix(matrix [][]int, k int) int {
	ans := []int{}
	dp := make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))

		if i == 0 {
			dp[i][0] = matrix[i][0]
		} else {
			dp[i][0] = max(matrix[i][0], matrix[i][0]+dp[i-1][0])
		}

		ans = append(ans, matrix[i][0])
		ans = append(ans, dp[i][0])
	}

	for i := 1; i < len(matrix[0]); i++ {
		dp[0][i] = max(matrix[0][i], matrix[0][i]+dp[0][i-1])
		ans = append(ans, matrix[0][i])
		ans = append(ans, dp[0][i])
	}

	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			dp[i][j] = max(matrix[i][j], max(matrix[i][j]+dp[i-1][j], max(matrix[i][j]+dp[i][j-1], matrix[i][j]+dp[i-1][j]+dp[i][j-1]+dp[i-1][j-1])))
			ans = append(ans, dp[i][j])
			ans = append(ans, matrix[i][j])
		}
	}

	return floor(ans, k)
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func floor(nums []int, k int) int {
	sort.Ints(nums)
	for i := len(nums) - 1; i >= 0; i-- {
		if nums[i] <= k {
			return nums[i]
		}
	}
	return 0
}

// @lc code=end

// 1. error 13/36
// @lc code=start
func maxSumSubmatrix(matrix [][]int, k int) int {
	ans := math.MinInt64
	dp := make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))

		if i == 0 {
			dp[i][0] = matrix[i][0]
		} else {
			dp[i][0] = max(matrix[i][0], matrix[i][0]+dp[i-1][0])
		}

		if dp[i][0] <= k {
			ans = max(ans, dp[i][0])
		}
	}

	for i := 1; i < len(matrix[0]); i++ {
		dp[0][i] = max(matrix[0][i], matrix[0][i]+dp[0][i-1])
		if dp[0][i] <= k {
			ans = max(ans, dp[0][i])
		}
	}

	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[0]); j++ {
			dp[i][j] = max(matrix[i][j], max(matrix[i][j]+dp[i-1][j], max(matrix[i][j]+dp[i][j-1], matrix[i][j]+dp[i-1][j]+dp[i][j-1]+dp[i-1][j-1])))

			if dp[i][j] <= k {
				ans = max(ans, dp[i][j])
			}
		}
	}

	return ans
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// @lc code=end

